package s6_排序算法.sort1_交换排序;

import s6_排序算法.BaseSort;

import java.util.Arrays;

/**
 * @author wisdomelon
 * @date 2020/7/29 0029
 * @project data_study
 * @jdk 1.8
 * 快速排序
 */
public class QuickSort extends BaseSort {

    public static void main(String[] args) {
        //int arr[] = simple();
        int arr[] = {0};
        System.out.println(Arrays.toString(arr));
        new QuickSort().asc(arr);
        System.out.println(Arrays.toString(arr));
    }


    @Override
    public void asc(int[] arr) {

        System.out.println("QuickSort-------------------------------");
        long s = System.currentTimeMillis();

        quickSort(arr, 0, arr.length-1);

        long e = System.currentTimeMillis();
        System.out.println("QuickSort: " + (e-s) + "ms");
    }

    /**
     * 快速排序
     * @param arr
     * @param left
     * @param right
     */
    private void quickSort(int[] arr, int left, int right) {
        int l = left; // 左下标
        int r = right; // 右下标
        int pivot = arr[(left + right) / 2];  // 中位数

        while(l < r) { //
            // 从左往右进行查找，直到找到比中位数大的数据的下标
            while(arr[l] < pivot) {
                l++;
            }
            // 从右往左进行查找，直到找到比中位数小的数据的下标
            while(arr[r] > pivot) {
                r--;
            }
            // 如果左边的索引值不小于右边的索引值，说明此时已经交换完成了
            if(l >= r) {
                break;
            }
            // 将 左边的数 和 右边的数 进行交换
            int temp = arr[r];
            // 交换之后，右边的当前数会比中位数大
            arr[r] = arr[l];
            // 交换之后，左边当前的数会比中位数小
            arr[l] = temp;
            // 交换后，如果左边的值等于中位数，则让右下标前移一位
            if(arr[l] == pivot) {
                r--;
            }
            // 交换后，如果右边的值等于中位数，则让左下标后移一位
            if(arr[r] == pivot) {
                l++;
            }
        }

        if(l == r) {
            l++;
            r--;
        }

        // 向左递归
        if(left < r) {
            quickSort(arr, left, r);
        }
        // 向右递归
        if(right > l) {
            quickSort(arr, l, right);
        }


    }
}
